package leetcode.hot100;

import leetcode.tester.Tester;

import java.io.IOException;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 560. 和为K的子数组
 * https://leetcode.cn/problems/subarray-sum-equals-k/?envType=study-plan-v2&envId=top-100-liked
 *
 * @author Liu Yicong
 * @date 2025/10/14
 */
public class Hot10SubstrSubarraySum {
	public static void main(String[] args) throws IOException {
		List<String> content = Files.readAllLines(Paths.get("src/data/Hot10SubstrSubarraySum.txt"));
		int[] inp = Arrays.stream(content.get(0).split(",")).mapToInt(Integer::parseInt).toArray();
		int k = Integer.parseInt(content.get(1));
		int ans = Integer.parseInt(content.get(2));

		Object[][] inputs = {
				new Object[]{new int[]{1, 1, 1}, 2},
				new Object[]{new int[]{1, 2, 3}, 3},
				new Object[]{new int[]{1, 2, 1, 2, 1}, 3},
				new Object[]{new int[]{-1, 2, 2, 1, 2, 3}, 3},
				new Object[]{new int[]{-1, -1, 1}, 1},
				new Object[]{new int[]{-1, -1, 1}, 0},
				new Object[]{inp, k}
		};
		Object[] outputs = {
				2, 2, 4, 4, 1, 1, ans
		};

		Tester.test(Tester.wrap(new Hot10SubstrSubarraySum()::subarraySumBF), inputs, outputs);
		Tester.test(Tester.wrap(new Hot10SubstrSubarraySum()::subarraySumDP), inputs, outputs);
		Tester.test(Tester.wrap(new Hot10SubstrSubarraySum()::subarraySumHash), inputs, outputs);
	}

	/**
	 * 使用暴力法求解
	 */
	public int subarraySumBF(int[] nums, int k) {
		int n = nums.length;
		int result = 0;
		for (int start = 0; start < n; start++) {
			int sum = 0;
			for (int end = 0; end < n - start; end++) {
				sum += nums[start + end];
				if (sum == k) {
					result++;
				}
			}
		}
		return result;
	}

	/**
	 * 前缀和DP
	 */
	public int subarraySumDP(int[] nums, int k) {
		int n = nums.length;
		if (n < 2) {
			return nums[0] == k ? 1 : 0;
		}

		int result = 0;
		int[] dp = new int[n];
		dp[0] = nums[0];
		for (int i = 1; i < n; i++) {
			dp[i] = dp[i - 1] + nums[i];
			int t = dp[i] - k;
			if (dp[i] == k) {
				result++;
			}
			for (int j = 0; j < i; j++) {
				if (dp[j] == t) {
					result++;
				}
			}
		}
		return result;
	}

	/**
	 * 前缀和 + 哈希
	 * 通过map来优化上面的代码
	 */
	public int subarraySumHash(int[] nums, int k) {
		int n = nums.length;
		if (n < 2) {
			return nums[0] == k ? 1 : 0;
		}

		int result = 0;
		Map<Integer, Integer> map = new HashMap<>();
		map.put(0, 1);
		int prefix = 0;
		for (int num : nums) {
			prefix += num;
			int t = prefix - k;
			result += map.getOrDefault(t, 0);
			map.put(prefix, map.getOrDefault(prefix, 0) + 1);
		}
		return result;
	}
}
